# -*- coding: utf-8 -*-
"""
作者: liuzaiqiang
邮箱: zaiqiangliu@163.com
地址: 新疆大学
创建时间: 2025/11/21 18:24
功能描述:

为append操作设定平摊成本为 3，通过 “信用额” 的增减确保总信用非负，从而证明平摊成本为 O (1)。
"""


class DynamicArrayAccounting:
    def __init__(self, initial_capacity=1):
        self.data = [None] * initial_capacity
        self.size = 0
        self.capacity = initial_capacity
        self.credit = 0  # 记录总信用额
        self.actual_costs = []  # 记录每次操作的真实成本
        self.amortized_costs = []  # 记录每次操作的平摊成本（设定为3）

    def resize(self):
        """扩容操作，返回复制元素的成本"""
        new_capacity = 2 * self.capacity
        copy_cost = self.size
        new_data = [None] * new_capacity
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data = new_data
        self.capacity = new_capacity
        return copy_cost

    def append(self):
        """添加元素操作，平摊成本设定为3"""
        amortized_cost = 3
        self.amortized_costs.append(amortized_cost)

        # 真实成本：基础操作（1） + 扩容成本（若需）
        base_cost = 1
        actual_cost = base_cost
        if self.size == self.capacity:
            copy_cost = self.resize()
            actual_cost += copy_cost
        self.size += 1
        self.actual_costs.append(actual_cost)  # 直接记录完整真实成本

        # 会计方法：更新信用额
        self.credit += amortized_cost - actual_cost
        assert self.credit >= 0, "信用额不能为负"

    def accounting_analysis(self, n):
        """执行n次append并分析"""
        for _ in range(n):
            self.append()
        total_actual_cost = sum(self.actual_costs)
        total_amortized_cost = sum(self.amortized_costs)
        return {
            "total_actual_cost": total_actual_cost,
            "total_amortized_cost": total_amortized_cost,
            "final_credit": self.credit,
            "amortized_cost_per_op": total_amortized_cost / n
        }


# 示例：执行20次append
array = DynamicArrayAccounting(initial_capacity=1)
result = array.accounting_analysis(20)
print("动态数组会计方法分析结果：")
print(f"总真实成本: {result['total_actual_cost']}")
print(f"总平摊成本: {result['total_amortized_cost']}")
print(f"最终信用额: {result['final_credit']}")
print(f"每次操作平摊成本: {result['amortized_cost_per_op']}（理论上为3）")